<body>

<h1>Task Graph in Charm++</h1>

This document attempts to explain the taskGraph library for the Charm++
programming system. The library is at a first-release stage.

<h2>Problems Solved</h2>

Task Graph is designed to make it easier to solve "directed information flow"
problems. As a trivial example, consider calculating the Fibonacci numbers. To
calculate a number fib(n), it needs to know the values of fib(n-1) and
fib(n-2).
<p>

The dependency representation for Fibonacci may look something like this:
<p>

<table>
<tr><th>X'th Fibonacci</th><th>Depends On</th></tr>

<tr><td>0</td><td>none</td></tr>
<tr><td>1</td><td>none</td></tr>
<tr><td>2</td><td>0, 1</td></tr>
<tr><td>3</td><td>1, 2</td></tr>
<tr><td>4</td><td>2, 3</td></tr>
</table>
<p>

And so on until the number you desire. It is not designed to solve problems
such as Jacobi relaxation; it is not an iterative framework. You could contort
the Jacobi program to using it by saying iteration N depends on iteration N-1,
but that would defeat much of the purpose of the framework.
<p>

<h2>Library Structure</h2>

There are three basic components to an application using the library:

<ol>
<li>Graph Generator
<li>Data/Solver Class
<li>taskGraph Library
</ol>

The graph generator is the controller of the whole process. It will generate
the base-case data/solver class instances, and pass them into the library with
no dependencies. Then, the graph generator will generate new data/solver
classes (and give them any static data they need to know; like their location
in the computation, etc) and pass it to the library with a list of
dependencies.
<p>

Once the library has received data/solver classes, it will gather up the other
data that each needs to solve itself (what the graph generator passed to it).
Once it has all the data gathered, it will fire off the data/solver class and
tell it to solve itself.
<p>

Once the class has solved itself, the library will leave it waiting there
for any other data/solver tasks which may depend on it. Your graph generator
can tell the library that a data/solver task will not be needed anymore and
to delete it. The library will do so. (NOTE! You can delete a solver that
has other solvers waiting on it for data! If that happens your computation
will hang. Only delete when you're sure nobody will depend on that data/solver
again.)
<p>

If your graph generator needs the results of a data/solver computation back in
order to generate new data/solvers (perhaps a deformation has occurred and
shifted the area occupied by new data/solvers), then your data/solver class
must send the data your graph generator needs to it. You may also have the
library send the whole data/solver class instance back to your graph
generator, but it is messier than sending just the data you need.
<p>

<h2>How-to</h2>

This section gives a short how-to write a taskGraph application, using the
Fibonacci example. I am assuming you are already familiar with Charm++
programming, if you are not you'll need to be at least familiar enough with
it to write a simple program, like Jacobi, before this how-to will be of use
to you.
<p>

The following steps are the minimal steps needed for a taskGraph program;

<ul>
<li>A graph generator. This can be your main chare, or you could spawn any
sort of other Charm++ construct to generate the graph.
<li>A data/solver class, inherited off the taskGraphSolver class.
</ul>

The generator has three basic phases; initialization, generation, and results
collection. For instance, a generator may look like:

<pre>
class main : public Chare {
  public:
    main(CkArgMsg *m) {
      CkArrayID firstTaskGraph = yourSolver::newTaskGraph();
      ...
      yourSolver base(firstTaskGraph, 0);
      base.startTask();
      yourSolver next(firstTaskGraph, 1);
      next.dependsOn(0);
      next.startTask();
    }
    void results(int value) {
      ckout << "A task completed and sent in the result " << value << endl;
    }
};
</pre>

The taskGraphSolver class is an abstract class that allows the library to pass
around your data/solver class with ease. taskGraphSolver contains the
following methods;
<p>

<table>

<tr><td width=40%>
taskGraphSolver(CkArrayID, int x)<br>
taskGraphSolver(CkArrayID, int x, int y)<br>
taskGraphSolver(CkArrayID, int x, int y, int z)<br>
</td><td>
The constructor of a taskGraphSolver needs to know which running
taskGraph it is related to, thus you must pass it the CkArrayID of that
instance.
</td></tr>

<tr><td>
void pup(PUP::er &p)
</td><td>
The pack and unpack routine of the class. You must override this routine and
pack all the data your class contains. This allows the library to move your
class across processors, so work can be distributed from wherever it is
generated to where it should be run.
</td></tr>

<tr><td>
void solve(int count, taskGraphSolver *data[])
</td><td>
The solve function is an abstract function. You must override this function
and make it run the computation you need run. Note that the data you get
passed in is in no particular order.<p>

If you need to send information back to your graph generator, this is the
function to do it in.
</td></tr>

<tr><td>
void setup()
</td><td>
The setup function is an abstract function. It is called instead of solve when
a task has no dependences. You can use this function to setup information, and
to send information back to your graph generator.
</td></tr>

<tr><td>
void dependsOn(int x)<br>
void dependsOn(int x, int y)<br>
void dependsOn(int x, int y, int z)<br>
</td><td>
This trio of functions are defined in taskGraphSolver. They are used to
indicate that the current task object depends on these other task objects
defined by index x,y,z.
</td></tr>

<tr><td>
CkArrayID newTaskGraph()
</td><td>
This function is defined in taskGraphSolver, it is used to create a new
taskGraph. For each taskGraph you need to call this function, and will
then need to pass the CkArrayID you get to all tasks that are part of
this taskGraph.
</td></tr>

<tr><td>
void startTask()
</td><td>
This function is defined in taskGraphSolver. It will take the inerhited object
you have created and fire it off as a task. If this task had any dependences,
you need to have called dependsOn() before calling this function.
</td></tr>

<tr><td>
void removeTask()
</td><td>
This function is defined in taskGraphSolver. It will remove the task from the
library's management. Be careful, if you remove a task that others depend on,
your computation will hang!
</td></tr>

</table>
<p>

For a simple example, check out a current CVS charm build, and look at
the charm/pgms/charm++/taskGraph/fib/ example. Fib does what is described
here with one addition; it keeps track (in the main chare) of how many
tasks are running (that's what the 'int pending' is used for). When the
count of tasks running hits 0, it knows that it's computation is done so
it exits the program with CkExit().

</html>
